package LearnAlgorithm.g_数学问题;

import java.util.ArrayList;
import java.util.Scanner;
import java.util.List;

/*
有些人认为，一个人的一生有三个周期，从他或她出生的那一天开始。
这三个周期是身体周期、情感周期和智力周期，它们的周期分别为23天、28天和33天。
在一个周期的每个周期中都有一个峰值。
在一个周期的高峰期，一个人在相应的领域（身体、情感或心理）表现最佳。
例如，如果是心理曲线，思维过程会更敏锐，注意力也会更集中。
由于三个周期具有不同的周期，因此三个周期的峰值通常出现在不同的时间。

我们想确定任何人何时出现三重峰值（所有三个周期的峰值都发生在同一天）。
对于每个周期，您将获得从当年年初开始出现峰值（不一定是第一个）的天数。

您还将获得一个日期，用当前年份开始后的天数表示。
您的任务是确定从给定日期到下一个三重高峰的天数。给定的日期不计算在内。
例如，如果给定的日期是10，下一个三重峰值出现在第12天，那么答案是2，而不是3。
如果在给定日期出现三重高峰，则应给出下一次出现三重峰值的天数。




您将收到许多案例。每种情况的输入由一行四个整数p、e、i和d组成。
值p、e和i分别是从当年开始身体、情绪和智力周期达到峰值的天数。
值d是给定的日期，可能小于p、e或i中的任何一个。
所有值都是非负的，最多365，您可以假设在给定日期的21252天内会出现三重峰值。
输入的结束由这一行表示：p=e=i=d=-1。




对于每个测试用例，打印用例编号，然后打印一条消息，指示下一个三重峰值的天数，格式为：
Case 1: the next triple peak occurs in 1234 days.
即使答案是1，也要使用复数形式“days”。



0 0 0 0
Case 1: the next triple peak occurs in 21252 days.
4 5 6 7
Case 4: the next triple peak occurs in 16994 days.




即一元线性同余方程组问题：
x ≡ p (mod 23)					(1式)
x ≡ e (mod 28)					(2式)
x ≡ i (mod 33)					(3式)
	若给的d正好就是x，那么答案输出“21252”；
	若给的d大于x，那么答案输出“x + 21252”
 */
public class h三重高峰 {
	public static void main(String[] args) {
		try {
			new h三重高峰().deal();
			/*
0 0 0 0
0 0 0 100
4 5 6 7
-1 -1 -1 -1
			 */
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
	}
	
	public void deal() throws Exception {
		Scanner scanner = new Scanner(System.in);
		int t = 1;
		List<long[]> aList = new ArrayList<long[]>();
		List<Long> dList = new ArrayList<Long>();
		while (scanner.hasNext()) {
//			long[] a = new long[] {scanner.nextLong(), scanner.nextLong(), scanner.nextLong()};
			long[] a = {scanner.nextLong(), scanner.nextLong(), scanner.nextLong()};
			long d = scanner.nextLong();
			if (a[0] == -1 && a[1] == -1 && a[2] == -1 && d == -1) {
				break;
			} else {
				aList.add(a);
				dList.add(d);
			}
		}
		for (int i = 0; i < aList.size(); i++) {
			long[] a = aList.get(i);
			long d = dList.get(i);
//			long[] m = new long[] {23, 28, 33};
			long[] m = {23, 28, 33};
			long res = ExtGcd.linearEquationGroup(a, m);
			while (res <= d) {
				res += 21252;
			}
			System.out.println("Case " + (t++) + ": the next triple peak occurs in " + (res - d) + " days.");
		}
	}
	
	
	
	private static class ExtGcd {
		static long x;
		static long y;
		public static long gcdEx(long a, long b) {
			if (b == 0) {
				x = 1;
				y = 0;
				return a;
			}
			long res = gcdEx(b, a % b);
			long x1 = x;
			x = y;
			y = x1 - a / b * y;
			return res;
		}
		public static long linearEquation(long a, long b, long m) throws Exception {
			long d = gcdEx(a, b);
			if (m % d != 0) {
				throw new Exception("无解");
			}
			long n = Math.abs(m / d);
			x *= n;
			y *= n;
			return d;
		}
		public static long linearEquationOriginalEquation(long a, long b, long m) throws Exception {
			long d = gcdEx(a, b);
			if (m % d != 0) {
				throw new Exception("无解");
			}
//			long n = Math.abs(m / d);
			long n = m / d;
			x *= n;
			y *= n;
			return d;
		}
		public static long firstSolution(long a, long b, long m) throws Exception {
			long d = gcdEx(a, b);
			if (m % d != 0) {
				throw new Exception("无解");
			}
			b = b / d;
			x = (x % b + b) % b;
			return x;
		}
		public static long inverseElement(long a, long n) throws Exception {
			linearEquation(a, n, 1);
			x = (x % n + n) % n;
			return x;
		}
		public static long linearEquationGroup(long[] a, long[] m) throws Exception {
			int len = a.length;
			if (len == 0 && a[0] == 0) {
				return m[0];
			}
			for (int i = 1; i < len; i++) {
				long a2_a1 = a[i] - a[i - 1];
				long d = linearEquationOriginalEquation(m[i - 1], -m[i], a2_a1);
				long x0 = a[i - 1] + m[i - 1] * x;
				long lcm = (m[i - 1] * m[i]) / d;
				a[i] = (x0 % lcm + lcm) % lcm;
				m[i] = lcm;
			}
			return a[len - 1] % m[len - 1];
		}
	}
}
